package com.suduku.view.data;

import java.util.Random;

/**
 * 功能描述: 生成数独数据 <br/>
 */
public class RandSudoData {

    private final int[][] array = new int[9][9];   // 得到一个9*9的数独
    private final int[][] shuDu = new int[9][9]; // 挖空array数组中的数字
    private final int[] row = new int[9]; // 每一行的个数
    private final int[] col = new int[9];  // 每一列的个数
    private final int[] places = new int[9];  // 每一个九宫格的个数
    private boolean flag = false;
    boolean emptyRow = false;
    boolean emptyCol = false;
    boolean emptyLaces = false;

    /**
     /**
     * 功能描述: 通过难度，随机获取数独数据 <br/>
     *
     * @param grade [1-40]:简单；(40-45]:中等；(45-50]:困难；(50-55]:专家
     * @return "java.lang.String"
     */
    public String randDataStr(int grade) {
        int[][] a = randData(grade);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                sb.append(a[i][j]);
            }
        }
        return sb.toString();
    }

    /**
     * 功能描述: 通过难度，随机获取数独数据 <br/>
     *
     * @param grade [1-40]:简单；(40-45]:中等；(45-50]:困难；(50-55]:专家
     * @return "int[][]"
     */
    public int[][] randData(int grade) {
        generateData();
        while (grade > 0) {
            //随机抽到x,y
            int x = new Random().nextInt(9);
            int y = new Random().nextInt(9);
            //若x,y没有被挖空则挖空x,y
            if (shuDu[x][y] != 0) {
                row[x]--;
                col[y]--;
                places[(y / 3) * 3 + x / 3]--;
                if ((row[x] == 0 && emptyRow) || (col[y] == 0 && emptyCol) || (places[(y / 3) * 3 + x / 3] == 0 && emptyLaces)) {
                    System.out.println(x + " " + y + " 不可以");
                    continue;
                } else {
                    shuDu[x][y] = 0;
                    grade = grade - 1;
                }
                if (row[x] == 0)
                    emptyRow = true;
                if (col[y] == 0)
                    emptyCol = true;
                if (places[(y / 3) * 3 + x / 3] == 0)
                    emptyLaces = true;
            }
        }
        return shuDu;
    }



    /**
     * 功能描述: 生成数独数据 <br/>
     */
    private void generateData() {
        //初始化数组
        for (int i = 0; i < 9; i++) {
            row[i] = col[i] = places[i] = 9;
        }
        rand();
        // 解题
        dfs(array, 0);
    }

    /**
     * 功能描述: 通过dfs获取第一个解 <br/>
     *
     * @param array 数独数据
     * @param n 候选数字
     */
    private void dfs(int[][] array, int n) {
        if (n < 81) {
            if (flag) return;
            int x = n / 9;//x第N个数的横坐标
            int y = n % 9;//y第N个数的纵坐标
            if (array[x][y] == 0) {
                //若第N个数为0，没有被填过，则判断0~9是否能被填
                for (int i = 1; i < 10; i++) {
                    if (check(array, x, y, i)) {
                        //第N个数可以填i，填入然后dfs
                        array[x][y] = i;
                        dfs(array, n + 1);
                        //dfs回溯
                        array[x][y] = 0;
                    }
                }
            } else {
                dfs(array, n + 1);
            }
        } else {
            flag = true;
            //将获得的数组放入shuDu中然后再挖空
            for (int i = 0; i < 9; i++) {
                System.arraycopy(array[i], 0, shuDu[i], 0, 9);
            }
        }
    }

    /**
     * 功能描述: 随机给数 <br/>
     */
    private void rand() {
        int t = 0;
        //t=14不随机性太高，容易产生没有解的数独，经过参考资料发现，当t=6的时候，几乎100%有解
        while (t < 6) {
            int x = new Random().nextInt(9);
            int y = new Random().nextInt(9);
            int i = new Random().nextInt(9) + 1;
            if (array[x][y] == 0) {
                if (check(array, x, y, i)) {  //判断数是否能填
                    array[x][y] = i;
                    t++;
                }
            }
        }
    }

    /**
     * 功能描述: 判断array[x][y]上是否能放num <br/>
     *
     * @param array 数组
     * @param x     x
     * @param y     x
     * @param num   num
     * @return "boolean"
     */
    private boolean check(int[][] array, int x, int y, int num) {
        //横竖是否有num
        for (int i = 0; i < 9; i++) {
            if (array[x][i] == num || array[i][y] == num) {
                return false;
            }
        }
        for (int i = (x / 3) * 3; i < (x / 3 + 1) * 3; i++) {
            for (int j = (y / 3) * 3; j < (y / 3 + 1) * 3; j++) {
                if (array[i][j] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}
